package cn.datastructure.b_node;

import java.util.Objects;

import cn.datastructure.AbstractList;
import cn.datastructure.List;

/**
 * @author summit
 * @since 2022/6/24 14:24
 */
public class LinkedList<E> extends AbstractList<E> {
    private Node<E> first;

    private Node<E> last;

    private static class Node<E> {
        E element;

        Node<E> prev;

        Node<E> next;

        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }

        public E getElement() {
            return element;
        }

        public void setElement(E element) {
            this.element = element;
        }

        public Node<E> getPrev() {
            return prev;
        }

        public void setPrev(Node<E> prev) {
            this.prev = prev;
        }

        public Node<E> getNext() {
            return next;
        }

        public void setNext(Node<E> next) {
            this.next = next;
        }
    }

    @Override
    public void clear() {
        first = null;
        last = null;
        size = 0;
    }

    /**
     * 获取index位置对应节点对象
     * @param index 索引
     * @return 结果
     */
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }


    @Override
    public void add(int index, E element) {
        // index =0 size =0
        if (size == index) {
            Node<E> oldLast = last;
            last = new Node<>(oldLast, element, null);
            // 这是链表添加的第一个元素
            if (oldLast == null) {
                first = last;
            } else {
                oldLast.next = last;
            }
        } else {
            Node<E> node = node(index - 1);
            Node<E> next = node.next;
            node.next = new Node<>(node, element, next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
         // index = 0
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (Objects.equals(element, first.element)) {
                return i;
            }
            node = node.next;
        }
        return ELEMENT_NOT_FOUND;
    }
}
